
/**
 * 排序算法
 *
 * @author agstar
 */
public class Sort {


    /**
     * 冒泡排序
     *
     * @author agstar
     * @date 2020/5/19 23:03
     */
    public void popSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    /**
     * 选择排序
     *
     * @author agstar
     * @date 2020/5/19 23:05
     */
    public void selectSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }

    }


    /**
     * 插入排序
     *
     * @author agstar
     * @date 2020/5/19 23:04
     */
    public void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < arr[i - 1]) {
                int pos = -1;
                for (int j = 0; j < i; j++) {
                    if (arr[j] > arr[i]) {
                        pos = j;
                        break;
                    }
                }
                int temp = arr[i];
                for (int k = i - 1; k >= pos; k--) {
                    arr[k + 1] = arr[k];
                }
                arr[pos] = temp;
            }
        }
    }

    /**
     * 快速排序
     *
     * @author agstar
     * @date 2020/5/19 23:06
     */
    public void quickSort(int[] data, int first, int last) {
        // 如果数组要排序的开始下标等于或大于结束下标，数组排序完毕了
        if (first >= last) {
            return;
        }
        int low = first;
        int high = last;
        // 选取数组中的第一个元素作为中间值
        int midValue = data[low];
        //第一步排序先把中间值得下标找出来，从两头开始找
        //结果是大于midValue的所有数据在右边，小于midValue的所有数据在左边
        while (low < high) {
            //从后往前找，如果值一直大于等于中间值就一直往前找
            while (low < high && data[high] >= midValue) {
                high--;
            }
            //跳出循环后表示当前位置值比中间值小，应该将其放在中间值的左边，和low交换，覆盖data[low]的值
            //此时data[high]的就是多余的
            if (low < high) {
                data[low] = data[high];
            }
            //开始从前向后循环，如果值始终小于midValue中间值，就一直往后循环
            while (low < high && data[low] < midValue) {
                low++;
            }
            //如果找到一个值比中间值大，将其放到high上
            if (low < high) {
                data[high] = data[low];
            }
        }
        // 到这一步时low==high,两者都是midValue的下标所在
        data[low] = midValue;
        //以midValue所在下标为界，循环数组的前半部分
        quickSort(data, first, low - 1);
        //以midValue所在下标为界，循环数组的后半部分
        quickSort(data, low + 1, last);
    }

}